public class MyList implements List {

	private LinkedList list;
	
	public MyList() {
		list = new LinkedList();
	}

	public int size( ) {
		return list.size();
	}
    

    public boolean isEmpty( ) {
		return list.isEmpty();
	}
    

    public boolean contains( Object x ) {
		return ( list.find( x, null ) != null );
	}
    

    public boolean add( Object x ) {
		list.insert( x, list.getLast() );
		return true;
	}


    public boolean remove( Object x ) {
		ListNode n = list.find( x, null );
		if ( n != null ) {
			list.remove( n ); 
			return true;
		}
		else {
			return false;
		}
	}

	
    public void clear( ) {
		list.clear();
	}
   

    public Iterator iterator( ) {
		return new MyListIterator( this, list.getFirst() );
	}
   

    public Object [ ] toArray( ) {
		Object[] arr = new Object[ size() ];

		int i = 0;
		ListNode n = list.getFirst();
		while ( n != null ) {
			arr[ i++ ] = n.getElement();
			n = n.getNext();
		}

		assert i == arr.length;

		return arr;
	}


    public Object get( int idx ) {
		ListNode n = findIndex( idx );
		if ( n == null ) {
			throw new IndexOutOfBoundsException();
		}
		return n.getElement();
	}
   

    public Object set( int idx, Object newVal ) {
		ListNode n = findIndex( idx );
		if ( n == null ) {
			throw new IndexOutOfBoundsException();
		}
		Object oldVal = n.getElement();
		n.setElement(newVal);
		return oldVal;
	}


    public ListIterator listIterator( int pos ) {
		return new MyListIterator( this, findIndex( pos ) );
	}

	private ListNode findIndex( int idx ) {
		if ( idx < 0 ) {
			throw new IndexOutOfBoundsException();
		}	
		ListNode cur = list.getFirst();
		// skip idx nodes
		for (int i=0; i < idx && cur != null; ++i) {
			cur = cur.getNext();
		}
		return cur;
	}


	private static class MyListIterator implements ListIterator {

		private static final int NEXT = 1;
		private static final int PREV = 2;
		private static final int NONE = 3;

		private MyList mylist;
		private ListNode pos;
		private int lastOp;

		public MyListIterator( MyList _mylist, ListNode _pos ) {
			mylist = _mylist;
			pos = _pos;
			lastOp = NONE;
		}

		public boolean hasNext() {
			return ( pos != null );
		}

		public Object next() {
			if ( !hasNext() ) {
				throw new IllegalStateException();
			}

			Object e = pos.getElement();
			pos = pos.getNext();
			lastOp = NEXT;
			return e;
		}

		public boolean hasPrevious() {
			if ( pos != null ) {
				return ( pos.getPrevious() != null );
			}
			else {
				return ( mylist.list.getLast() != null );
			}
		}

		public Object previous() {
			if ( !hasPrevious() ) {
				throw new IllegalStateException();
			}
			
			if ( pos != null ) {
				pos = pos.getPrevious();
			}
			else {
				pos = mylist.list.getLast();
			}

			lastOp = PREV;
			return pos.getElement();
		}

		public void remove() {
			switch (lastOp) {
				case NONE:
						throw new IllegalStateException();
				case NEXT:
                        if ( pos != null ) {
						    mylist.list.remove( pos.getPrevious() );
                        }
                        else {
                            mylist.list.remove( mylist.list.getLast() );
                        }
						break;
				case PREV:
						ListNode oldPos = pos;
						pos = pos.getNext();
						mylist.list.remove( oldPos );
						break;
			}
            lastOp = NONE;
		}
	}

}